home *** CD-ROM | disk | FTP | other *** search
/ Gold Medal Software 2 / Gold Medal Software Volume 2 (Gold Medal) (1994).iso / os2 / cpostsrc.arj / LIST.C < prev    next >
C/C++ Source or Header  |  1992-08-08  |  9KB  |  360 lines
  1. /*------------------------------------------------------------------
  2.  * list.c : list functions
  3.  *------------------------------------------------------------------
  4.  * 10-19-88 originally by Patrick J. Mueller
  5.  * 08-07-92 fixed up by Patrick J. Mueller
  6.  *------------------------------------------------------------------*/
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12. #include "list.h"
  13.  
  14. /*------------------------------------------------------------------
  15.  * create a list
  16.  *------------------------------------------------------------------*/
  17. List *ListCreate(
  18.    int              itemSize,
  19.    ListCompareFunc *cmpFunc,
  20.    ListNoMemFunc   *memFunc
  21.    )
  22.    {
  23.    List *list;
  24.  
  25.    /*---------------------------------------------------------------
  26.     * sanity check
  27.     *---------------------------------------------------------------*/
  28.    if (!itemSize || !cmpFunc)
  29.       return NULL;
  30.  
  31.    /*---------------------------------------------------------------
  32.     * allocate structure
  33.     *---------------------------------------------------------------*/
  34.    list = malloc(sizeof(List));
  35.    if (!list)
  36.       {
  37.       if (memFunc)
  38.          memFunc();
  39.  
  40.       return NULL;
  41.       }
  42.  
  43.    /*---------------------------------------------------------------
  44.     * set fields
  45.     *---------------------------------------------------------------*/
  46.    list->head     = NULL;
  47.    list->itemSize = itemSize;
  48.    list->count    = 0;
  49.    list->cmpFunc  = cmpFunc;
  50.    list->memFunc  = memFunc;
  51.  
  52.    return list;
  53.    }
  54.  
  55. /*------------------------------------------------------------------
  56.  * destroy a list
  57.  *------------------------------------------------------------------*/
  58. void ListDestroy(
  59.    List *list
  60.    )
  61.    {
  62.    ListNode *node;
  63.    ListNode *next;
  64.  
  65.    if (!list)
  66.       return;
  67.  
  68.    /*---------------------------------------------------------------
  69.     * destroy each node
  70.     *---------------------------------------------------------------*/
  71.    node = list->head;
  72.    while (node)
  73.       {
  74.       next = node->next;
  75.       free(node->pItem);
  76.       free(node);
  77.       node = next;
  78.       }
  79.  
  80.    /*---------------------------------------------------------------
  81.     * destroy list
  82.     *---------------------------------------------------------------*/
  83.    free(list);
  84.    }
  85.  
  86. /*------------------------------------------------------------------
  87.  * get number of items in list
  88.  *------------------------------------------------------------------*/
  89. int ListCount(
  90.    List *list
  91.    )
  92.    {
  93.    if (!list)
  94.       return 0;
  95.    else
  96.       return list->count;
  97.    }
  98.  
  99. /*------------------------------------------------------------------
  100.  * find an item
  101.  *------------------------------------------------------------------*/
  102. void *ListFind(
  103.    List *list,
  104.    void *pItem
  105.    )
  106.    {
  107.    ListNode *node;
  108.    int       cmp;
  109.  
  110.    if (!list || !pItem)
  111.       return NULL;
  112.  
  113.    /*---------------------------------------------------------------
  114.     * look for item
  115.     *---------------------------------------------------------------*/
  116.    for (node=list->head; node; node=node->next)
  117.       {
  118.       cmp = list->cmpFunc(pItem,node->pItem);
  119.  
  120.       if (0 == cmp)
  121.          return node->pItem;
  122.  
  123.       else if (cmp < 0)
  124.          return NULL;
  125.       }
  126.  
  127.    return NULL;
  128.    }
  129.  
  130. /*------------------------------------------------------------------
  131.  * add an item
  132.  *------------------------------------------------------------------*/
  133. void *ListAdd(
  134.    List      *list,
  135.    void      *pItem
  136.    )
  137.    {
  138.    ListNode *last;
  139.    ListNode *node;
  140.    ListNode *new;
  141.    int       cmp;
  142.  
  143.    if (!list || !pItem)
  144.       return NULL;
  145.  
  146.    /*---------------------------------------------------------------
  147.     * find insertion point
  148.     *---------------------------------------------------------------*/
  149.    last = NULL;
  150.    for (node=list->head; node; node=node->next)
  151.       {
  152.       cmp = (list->cmpFunc)(pItem,node->pItem);
  153.  
  154.       if (0 == cmp)
  155.          return NULL;
  156.  
  157.       else if (cmp < 0)
  158.          break;
  159.  
  160.       last = node;
  161.       }
  162.  
  163.    /*---------------------------------------------------------------
  164.     * allocate memory
  165.     *---------------------------------------------------------------*/
  166.    new = malloc(sizeof(ListNode));
  167.    if (new)
  168.       new->pItem = malloc(list->itemSize);
  169.  
  170.    if (!new || !new->pItem)
  171.       {
  172.       if (list->memFunc)
  173.          list->memFunc();
  174.       return NULL;
  175.       }
  176.  
  177.    /*---------------------------------------------------------------
  178.     * update count, copy item
  179.     *---------------------------------------------------------------*/
  180.    list->count++;
  181.    memcpy(new->pItem,pItem,list->itemSize);
  182.  
  183.    /*---------------------------------------------------------------
  184.     * link into list
  185.     *---------------------------------------------------------------*/
  186.    if (last)
  187.       {
  188.       new->next  = last->next;
  189.       last->next = new;
  190.       }
  191.  
  192.    else
  193.       {
  194.       new->next  = list->head;
  195.       list->head = new;
  196.       }
  197.  
  198.    return new->pItem;
  199.    }
  200.  
  201. /*------------------------------------------------------------------
  202.  * delete an item
  203.  *------------------------------------------------------------------*/
  204. void ListDelete(
  205.    List *list,
  206.    void *pItem
  207.    )
  208.    {
  209.    ListNode *last;
  210.    ListNode *node;
  211.    int      cmp;
  212.  
  213.    if (!list || !pItem)
  214.       return;
  215.  
  216.    /*---------------------------------------------------------------
  217.     * find node
  218.     *---------------------------------------------------------------*/
  219.    last = NULL;
  220.    for (node=list->head; node; node=node->next)
  221.       {
  222.       cmp = (list->cmpFunc)(pItem,node->pItem);
  223.       if (0 == cmp)
  224.          break;
  225.  
  226.       else if (cmp < 0)
  227.          return;
  228.  
  229.       last = node;
  230.       }
  231.  
  232.    /*---------------------------------------------------------------
  233.     * if not found, exit
  234.     *---------------------------------------------------------------*/
  235.    if (!node)
  236.       return;
  237.  
  238.    /*---------------------------------------------------------------
  239.     * unlink from list
  240.     *---------------------------------------------------------------*/
  241.    if (last)
  242.       {
  243.       if (last->next)
  244.          last->next = last->next->next;
  245.       else
  246.          last->next = NULL;
  247.       }
  248.  
  249.    else
  250.       list->head = node->next;
  251.  
  252.    /*---------------------------------------------------------------
  253.     * update count, destroy item
  254.     *---------------------------------------------------------------*/
  255.    list->count--;
  256.  
  257.    free(node->pItem);
  258.    free(node);
  259.    }
  260.  
  261. /*------------------------------------------------------------------
  262.  * iterate through items
  263.  *------------------------------------------------------------------*/
  264. void ListIterate(
  265.    List            *list,
  266.    ListIterateFunc *pIterateFunc,
  267.    void            *pUserData
  268.    )
  269.    {
  270.    ListNode *node;
  271.  
  272.    if (!list || !pIterateFunc)
  273.       return;
  274.  
  275.    for (node=list->head; node; node=node->next)
  276.       pIterateFunc(node->pItem,pUserData);
  277.    }
  278.  
  279. /*------------------------------------------------------------------
  280.  * test suite
  281.  *------------------------------------------------------------------*/
  282. #if defined(TEST)
  283.  
  284. /*------------------------------------------------------------------
  285.  * compare function
  286.  *------------------------------------------------------------------*/
  287. static int compareFunc(
  288.    void *overi1,
  289.    void *overi2
  290.    )
  291.    {
  292.    int *i1 = overi1;
  293.    int *i2 = overi2;
  294.  
  295.    if      (*i1 < *i2) return -1;
  296.    else if (*i1 > *i2) return  1;
  297.    else                return  0;
  298.    }
  299.  
  300. /*------------------------------------------------------------------
  301.  * iterate function
  302.  *------------------------------------------------------------------*/
  303. static void iterateFunc(
  304.    void *overI,
  305.    void *overCounter
  306.    )
  307.    {
  308.    int *pi       = overI;
  309.    int *pCounter = overCounter;
  310.  
  311.    printf("%5d : %5d\n",*pCounter,*pi);
  312.    *pCounter += 1;
  313.    }
  314.  
  315. /*------------------------------------------------------------------
  316.  *
  317.  *------------------------------------------------------------------*/
  318. int main(void)
  319.    {
  320.    List *iList;
  321.    int   i;
  322.    int   counter;
  323.  
  324.    iList = ListCreate(sizeof(int),compareFunc,NULL);
  325.  
  326.    printf("%d items\n",ListCount(iList));
  327.  
  328.    for (i= 1; i<10; i++)
  329.       ListAdd(iList,&i);
  330.  
  331.    for (i=20; i>10; i--)
  332.       ListAdd(iList,&i);
  333.  
  334.    for (i=0; i<=21; i++)
  335.       if (!ListFind(iList,&i))
  336.          printf("didn't find %d\n",i);
  337.  
  338.    printf("\n");
  339.    printf("%d items\n",ListCount(iList));
  340.    counter = 1;
  341.    ListIterate(iList,iterateFunc,&counter);
  342.  
  343.    for (i=-1; i<5; i++)
  344.       ListDelete(iList,&i);
  345.  
  346.    for (i=21; i>15; i--)
  347.       ListDelete(iList,&i);
  348.  
  349.    printf("\n");
  350.    printf("%d items\n",ListCount(iList));
  351.    counter = 1;
  352.    ListIterate(iList,iterateFunc,&counter);
  353.  
  354.    ListDestroy(iList);
  355.  
  356.    return 0;
  357.    }
  358.  
  359. #endif
  360.